package programmercarl.动态规划.C17;

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //
        int zeroNums,oneNums;
        int dp[][]=new int[m+1][n+1];
        //递推公式
        //dp[i][j]=max(dp[i][j],dp[i-zeroNums][j-oneNums]+1)
        //初始化
        for(String str:strs){
            zeroNums=0;
            oneNums=0;
            for(int i=0;i<str.length();i++){
                if(str.charAt(i)=='0'){
                    zeroNums++;
                }else{
                    oneNums++;
                }
            }
            //遍历顺序,没什么讲究
            for(int i=m;i>=zeroNums;i--){
                for(int j=n;j>=oneNums;j--){
                    dp[i][j]=Math.max(dp[i][j],dp[i-zeroNums][j-oneNums]+1);
                }
            }

        }
        return dp[m][n];
    }
}